package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/path-existence-queries-in-a-graph-i/
 * @create 2025/9/23 19:40
 * @since JDK17
 */

public class Solution72 {
    int[] f;
    int find(int x) {
        if (x != f[x]) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        f[fx] = fy;
    }

    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        int m = queries.length;
        boolean[] ans = new boolean[m];
        f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
        for (int l = 0, r = 1; r < n; ) {
            if (nums[r] - nums[l] <= maxDiff) {
                merge(l, r++);
            } else {
                while (nums[r] - nums[l] > maxDiff) {
                    l++;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            ans[i] = isSameSet(queries[i][0], queries[i][1]);
        }

        return ans;
    }
}
